CS229：02-线性回归

首先引入一些后面会用到的定理：

定义 1：定义函数$f: \Bbb R^{m \times n} \mapsto \Bbb R$，$A \in \Bbb R^{m \times n}$，定义

$$\nabla_Af(A)= \begin{bmatrix} \frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1n}}\\\ \vdots & \ddots & \vdots \\\ \frac{\partial f}{\partial A_{m1}} & \cdots & \frac{\partial f}{\partial A_{mn}} \end{bmatrix}$$

定义 2：矩阵的迹（Trace）：如果$A \in R^{n\times n}$方阵，那么$A$的迹，是$A$对角线元素之和

$$tr A = \sum_{i=1}^nA_{ii}$$

定理 1：$tr AB = tr BA$

定理 2：$tr ABC = tr CAB = tr BCA$

定理 3：$f(A)=tr AB \Rightarrow \nabla_Af(A)=B^T$

定理 4：$trA = tr A^T$

定理 5：$a \in R \Rightarrow tr a=a$

定理 6：$\nabla_AtrABA^TC=CAB+C^TAB^T$

线性回归

一些符号的改写

上一篇博客提到，梯度下降的每一步，对某个参数$\theta_i$，执行：

$$\displaystyle \theta_i:=\theta_i - \alpha\frac{\partial}{\partial \theta_i}J(\theta)$$

那么，$h_\theta(x)$的所有参数$\theta$可以表示成一列向量：

$$\theta = \left[ \begin{array}{c} \theta_0\\\ \theta_1\\\ \vdots\\\ \theta_n \end{array} \right] \in R^{n+1}$$

我们可以定义：

$$\nabla_\theta J = \left[ \begin{array}{c} \frac{\partial}{\partial \theta_0}J\\\ \frac{\partial}{\partial \theta_1}J\\\ \vdots\\\ \frac{\partial}{\partial \theta_n}J \end{array} \right] \in R^{n+1}$$

梯度下降过程可以表示成：

$$\theta:=\theta - \alpha\nabla_\theta J$$

其中，$\theta$和$\nabla_\theta J$都说是 n+1 维向量。

对于训练集中所有的输入${x^{(1)}},x^{(2)},…,x^{(m)}$，其中

$$x^{(i)} = \left[ \begin{array}{c} 1\\\ x_1^{(i)}\\\ \vdots\\\ x_n^{(i)}\\\ \end{array} \right] \in R^{n+1}$$

$h(x)=h_{\theta}(x)=\theta_0+\theta_1x_1+\theta_2x_2+…+\theta_nx_n$，可以表示成向量：

$$\left[ \begin{array}{c} h_\theta(x^{(1)})\\\ h_\theta(x^{(2)})\\\ \vdots\\\ h_\theta(x^{(m)})\\\ \end{array} \right] = \left[ \begin{array}{c} (x^{(1)})^T\theta\\\ (x^{(2)})^T\theta\\\ \vdots\\\ (x^{(m)})^T\theta\\\ \end{array} \right] = \left[ \begin{array}{c} (x^{(1)})^T\\\ (x^{(2)})^T\\\ \vdots\\\ (x^{(m)})^T \end{array} \right] \cdot \theta = X \cdot \theta$$

而

$$Y = \left[ \begin{array}{c} y^{(1)}\\\ y^{(2)}\\\ \vdots\\\ y^{(m)} \end{array} \right]$$

于是，

$$J(\theta) = \frac{1}{2}\sum_{i=1}^{m}(h(x^{(i)} - y^{(i)})^2)=\frac{1}{2}(X \cdot \theta - Y)^T(X \cdot \theta - Y)$$

推导过程

关于梯度下降法，可以直接简化为求梯度为 0 的位置，即求$\nabla_\theta J(\theta) = \vec{0}$

首先，简化：

$$\begin{align} \nabla_\theta J(\theta) & = \nabla_\theta\frac{1}{2}(X \cdot \theta - Y)^T(X \cdot \theta - Y)\\\ & =\frac{1}{2}\nabla_\theta tr(\theta^TX^TX\theta - \theta^TX^TY - Y^TX\theta + Y^TY)\\\ & =\frac{1}{2}[\nabla_\theta tr(\theta\theta^TX^TX) - \nabla_\theta tr(Y^TX\theta) - \nabla tr(Y^TX\theta)] \end{align}$$

其中，第一项：

$$\begin{align} \nabla_\theta tr(\theta\theta^TX^TX) & = \nabla_\theta tr(\theta I \theta^TX^TX) &\text{定理6, set: $\theta =^{set} A, I = B, X^TX=C$}\\\ & = X^TX\theta I + X^TX\theta I & \text{$CAB+C^TAB^T$}\\\ & = X^TX\theta + X^TX\theta \end{align}$$

第二项和第三项：

$$\nabla_\theta tr(Y^TX\theta) = X^TY\\\ (定理3，set:Y^TX = B, \theta = A)$$

所以：

$$\nabla_\theta J(\theta) = X^TX\theta - X^TY = 0\\\ \Rightarrow X^TX\theta = X^TY\\\$$

最后解得：

$$\theta = (X^TX)^{(-1)}X^TY$$

当然，以上的解是有限制的，只有当$X^TX$满秩时，才能够求逆。

如果非满秩，说明方程数量不够，也就是当需要 n 个参数时，却不够 n 个输入样本。